package com.hao.sort;

import java.util.Random;
/**
 * TODO
 * 插入排序
 * @author 97472
 * @version 1.0
 * @date 2021/5/12 14:14
 */
public class InsertSort {

    public static void main(String[] args) {
        // 从0-10000中获取10000个元素的数组
        Integer[] arr = SortUtils.getRandomArr(500000, 500000);
        long start1 = System.currentTimeMillis();
        swapSort(arr);
        long end1 = System.currentTimeMillis();
        System.out.println("花费时间："+(end1-start1));
    }
    public static void moveSort(Integer[] arr){
        for (int i = 1; i < arr.length; i++) {
            // 抽去后缀中的第一个元素
            Integer temp = arr[i];
            // 从右至左依次与前缀比较
            for (int j = i-1; j >= 0; j--) {
                // 如果前缀元素大于temp就将其往后移移位
                if (temp < arr[j]){
                    arr[j+1] = arr[j];
                }else{
                    //否则就将temp赋给小于temp的前缀元素后面
                    arr[j+1] = temp;
                    break;
                }
                // 如果前缀中所有的元素都移位了，就直接将temp赋给第一个位置
                if (j == 0){
                    arr[j] = temp;
                    break;
                }
            }
        }
    }
    public static void swapSort(Integer[] arr){
        for (int i = 1; i < arr.length; i++) {
            // 从2个元素开始，从右至左与前一个元素开始比较
            for (int j = i; j > 0; j--) {
                // 如果小于前一个元素就进行交换
                if (arr[j] < arr[j-1]){
                    exchange(arr,j,j-1);
                }else{
                    break;
                }
            }
        }
    }
    public static void exchange(Integer[] arr,Integer index1,Integer index2){
        Integer temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    public static void shellSort(Integer[] arr){
        // 获取增量
        Integer gap = arr.length / 2;
        // 如果有增量进行插入排序
        while (gap > 0){
            // 对从增量元素起，对后面的每一个元素进行插入排序。
            for (int i = gap; i < arr.length; i++) {
                // 获取当前元素的索引
                int j = i;
                // 获取当前元素的值
                Integer temp = arr[j];
                // 如果当前元素的索引大于等于增量值并且值小于小组内前一个元素的值
                while (j >= gap && temp < arr[j - gap]){
                    // 将小组内前面的元素后移动一位
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                // 最后结束后将值放入结束的当前元素索引上去
                arr[j] = temp;
            }
            // 增量减半
            gap /= 2;
        }
    }
    public static void printlnArr(Integer[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" " + arr[i]);
        }
        System.out.println();
    }
}
